class Solution
{
public:
    vector<vector<int>> constructProductMatrix(vector<vector<int>> &grid)
    {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> prefixProduct(m * n + 1, 1);
        vector<int> suffixProduct(m * n + 1, 1);
        int k = 0;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {

                prefixProduct[k + 1] = prefixProduct[k] * (grid[i][j] % 12345);
                prefixProduct[k + 1] %= 12345;
                ++k;
            }
        }
        k = m * n;
        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                suffixProduct[k - 1] = suffixProduct[k] * (grid[i][j] % 12345);
                suffixProduct[k - 1] %= 12345;
                --k;
            }
        }

        vector<vector<int>> result(m, vector<int>(n, 0));

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                int prefix = prefixProduct[i * n + j];
                int suffix = suffixProduct[i * n + j + 1];
                result[i][j] = prefix * suffix;
                result[i][j] %= 12345;
            }
        }
        return result;
    }
};